package leetcod_300;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class leetCode_20_MergeTwoSortedLists {
    //迭代
    public ListNode mergeTwoSortedListsByIterate(ListNode listNode1, ListNode listNode2) {
        ListNode dummy = new ListNode(0, null);
        ListNode ans = dummy;
        while (listNode1.next != null && listNode2.next != null) {
            if (listNode1.val > listNode2.val) {
                ans.next = listNode1;
                listNode1 = listNode1.next;
            }
            if (listNode1.val <= listNode2.val) {
                ans.next = listNode2;
                listNode2 = listNode2.next;
            }
            //迭代
            ans = ans.next;
        }
        ans.next = listNode1 == null ? listNode2 : listNode1;
        return ans.next;
    }

    //递归
    public ListNode mergeTwoSortedListsByRecursion(ListNode listNode1, ListNode listNode2) {
        if (listNode1 == null) {
            return listNode2;
        } else if (listNode2 == null) {
            return listNode1;
        } else if (listNode1.val < listNode2.val) {
            listNode1.next = mergeTwoSortedListsByRecursion(listNode1.next, listNode2);
            return listNode1;
        } else {
            listNode2.next = mergeTwoSortedListsByRecursion(listNode1, listNode2.next);
            return listNode2;
        }
    }
}
